
struct ListNode {
     int val;
      ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //exit
            if (head == nullptr || head->next == nullptr) return head;
    
            ListNode* prev = head;
            ListNode* cur  = head->next;
            while(cur->next){
                prev = cur;
                cur = cur->next;
            }
            //此时cur为最后一个节点，prev为倒数第二个节点
            prev->next = nullptr;
            cur->next = reverseList(head);
            return cur;
        }
    };

//reverselist的任务：反转链表
//只关注一个子问题：先反转最后的元素，接着剩下的再调用反转链表 ，return cur
//递归出口，当头节点为空，或者只有一个头节点时直接返回

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if(head == nullptr || head->next == nullptr)   return head;
            ListNode* newhead = reverseList(head->next);
            head->next->next=head;
            head->next = nullptr;
            return newhead;
        }
    
    };